package com.wtgroup.demo.leetcode.q031_下一个排列;

import com.wtgroup.demo.common.util.Tools;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/4/10 13:08
 */
public class Q031_My {

    public static void main(String[] args) {
        int[][] inputs = {
                {1, 2, 3},
                {3, 2, 1},
                {1, 1, 5},
                {1}
        };

        Q031_My exe = new Q031_My();
        for (int[] input : inputs) {
            exe.nextPermutation(input);
            Tools.printArray(input);
        }
    }

    /**
     * 独立思路
     *
     * 1. 从右至左, 停止条件: 右邻比自己大
     * 2. 替换: 右侧找比自己大的最近的.
     *
     * [复杂度]
     * 从右至左, N
     * 反转 N/2
     * O(n)
     */
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n-2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        // i==-1 => 当前是最大的->全部反转(最小的)
        if(i>0) {
            // i 右侧找最近大值
            int cur = nums[i];
            int minmax = n-1;
            // 找到比 cur 小的停, 取其前面的, 没有, 则最后一个 n-1 --> TOPERF: 自右向左找, 代码简单
            for (int j = i + 1; j < n; j++) {
                if (nums[j]<=cur) {
                    minmax = j-1;
                    break;
                }
            }
            swap(nums, i, minmax);
        }
        // i+1~. 反转
        reverse(nums, i+1);
    }

    // 右侧找最近大值代码简化
    public void nextPermutation_2(int[] nums) {
        int n = nums.length;
        int i = n-2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        // i==-1 => 当前是最大的->全部反转(最小的)
        if(i>0) {
            // i 右侧找最近大值
            int p = n;
            while (--p > i && nums[p] <= nums[i]) {}
            swap(nums, i, p);
        }
        // i+1~. 反转
        reverse(nums, i+1);
    }


    private void reverse(int[] nums, int start) {
        int n = nums.length;
        int i = start, j = n - 1;
        while (i < j) {
            swap(nums, i, j);
            i++; j--;
        }
    }

    private void swap(int[] nums, int i, int j) {
        nums[i] = nums[i] ^ nums[j];
        nums[j] = nums[i] ^ nums[j];
        nums[i] = nums[i] ^ nums[j];
    }



    // ----
    // public void nextPermutation_bak(int[] nums) {
    //     int n = nums.length;
    //     int i=n-2;
    //     for (i = n-2; i >= 0; i--) {
    //         int cur = nums[i];
    //         if (cur < nums[i+1]) {
    //             // 比右邻小, 右邻应该替换我
    //             nums[i] = nums[i + 1];
    //             // i+1 ~ n-1 和 cur 一起升序排列
    //             // cur 是基准, 比它小, 依次排放, 比它大, 先放cur再放它
    //             int k = i+1;
    //             for (int j = n - 1; j > i + 1; j--) {
    //                 if (nums[j] <= cur) {
    //                     nums[k++] = nums[j];
    //                 } else{
    //                     nums[k++] = cur;
    //                     nums[k++] = nums[j];
    //                     cur = Integer.MAX_VALUE; // +∞ 哨兵, 以后不会走此分支了, 0 <= nums[i] <= 100
    //                 }
    //             }
    //             // cur 比后面都大, 会漏掉->补偿
    //             if (cur != Integer.MAX_VALUE) {
    //                 nums[n-1] = cur;
    //             }
    //
    //             break;
    //         }
    //     }
    //
    //     // 整体降序 -> 最大的 -> 返回最小的 -> 反转
    //     if (i < 0) {
    //         reverse(nums);
    //     }
    //
    // }
}
